package sword.offer;

import java.util.*;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ThirtyTwo3 {
    // 利用双向队列来存储数据 当数据存在反转的情况 要考虑双向队列 或者双队列
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            if (Objects.isNull(root)) {
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>(){{add(root);}};
            List<List<Integer>> res = new ArrayList<>();
            int floor = 1;
            while(!queue.isEmpty()){
                LinkedList<Integer> r = new LinkedList<>();
                int size = queue.size(); // 细节啊~！！！ 或者for循环的时候 给i赋值size i--
                for (int i=0; i<size; i++){
                    TreeNode curNode = queue.poll();
                    if(floor % 2 == 0) r.addFirst(curNode.val);
                    else r.addLast(curNode.val);
                    if(Objects.nonNull(curNode.left)) {queue.add(curNode.left);}
                    if(Objects.nonNull(curNode.right)) {queue.add(curNode.right);}
                }
                floor++;
                res.add(r);
            }
            return res;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
